package org.example.minCircular;

import java.util.ArrayList;
import java.util.List;

/**
 * 最短环形计算
 */
public class MinCircular {
    // 计算两点之间的距离
    private static double distance(int[] p1, int[] p2) {
        return Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2));
    }

    // 计算所有可能的连接方式的周长，并返回最小值
    public static double minPerimeter(int[][] points) {
        int n = points.length;
        double minPerimeter = Double.MAX_VALUE;

        // 使用排列算法（全排列）生成所有可能的连接方式
        List<List<Integer>> permutations = generatePermutations(n);

        // 遍历所有可能的连接方式
        for (List<Integer> permutation : permutations) {
            double perimeter = 0;
            for (int i = 0; i < n - 1; i++) {
                // 计算当前点与下一个点之间的距离，并加到周长中
                perimeter += distance(points[permutation.get(i)], points[permutation.get(i + 1)]);
            }
            // 将最后一个点与第一个点之间的距离也加到周长中
            perimeter += distance(points[permutation.get(n - 1)], points[permutation.get(0)]);

            // 更新最小周长
            minPerimeter = Math.min(minPerimeter, perimeter);
        }

        return minPerimeter;
    }

    // 使用递归回溯生成所有可能的排列（不包含重复）
    private static List<List<Integer>> generatePermutations(int n) {
        List<List<Integer>> permutations = new ArrayList<>();
        backtrack(new ArrayList<>(), permutations, n, new boolean[n]);
        return permutations;
    }

    private static void backtrack(List<Integer> current, List<List<Integer>> permutations, int n, boolean[] used) {
        if (current.size() == n) {
            permutations.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                current.add(i);
                backtrack(current, permutations, n, used);
                current.remove(current.size() - 1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[][] points = {{0, 1}, {1, 0}, {1, 1}, {0, 0}};
        double minPerimeter = minPerimeter(points);
        System.out.println("最短环形周长是：" + minPerimeter);
    }
}
